
\documentclass[a4paper,10pt]{article}
\usepackage{color}
% \usepackage{fancyhdr}
\usepackage[utf8]{inputenc}

\usepackage{enumerate}
\usepackage{latexsym}
\usepackage{amssymb}
\usepackage{ulem}
% \usepackage{ifsym}
\usepackage{graphicx}
\usepackage[margin=3cm]{geometry}

%\renewcommand{\headheight}{16pt}

%\newcommand{\HRule}{\rule{\linewidth}{0.1mm}}

\begin{document}

%\begin{titlepage}
\begin{center}
	\textsc{\Large Distributed Database Systems (WS 11/12) }\\[0.3cm]
	\textsc{\large Assignment 5}\\[1cm]
        Adam Grycner\\
        Szymon Matejczyk\\
        Guo Xinyi\\
        Yu Chenying\\[1cm]
        \today\\[1cm]
        \rule{\linewidth}{0.1mm}\\
 	%\HRule\\
%	\HRule\\[2cm]
	
\end{center}




\section{Exercise 5.1: Discussion}
  \begin{enumerate}[1.]
  \item Getting votes from the majority of nodes will be still possible even if there's node failures or partitioning.
  \item It ensures 1-copy-serializability. If $Q_R+Q_U<=R$, then it's possible to execute write and read at the same time which will result in collision. So is $Q_U+Q_U<=R$, two different writes may occur at the same time.
  \item
    \begin{itemize}
         \item ROWA : strong
         \item primary copy : strong
         \item majority consensus : strong
         \item dynamic voting : strong
         \item tree quorum : strong
         \item reconfigurable tree quorum : strong
         \item data patches : eventual
         \item snapshot replication : eventual
         \item epidemic replication : weak
     \end{itemize}
  \end{enumerate}

\section{Exercise 5.2: ROWA and allocation}
\scriptsize
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
node(s) having the copy of A & remote read costs & update costs & total costs\\
\hline
 N1 & 4*110 & 6*20 & 560\\
 \hline
 N2 & 4*100 & 6*10 & 460\\
 \hline
 N3 & 4*90 & 6*30 & 540\\
 \hline
 N4 & 4*120 & 6*30 & 660\\
  \hline
 N1,N2 & 4*70 & 6*30 & 460\\
  \hline
 N1,N3 & 4*60 & 6*20 & 360\\
  \hline
 N1,N4 & 4*90 & 6*20 & 480\\
  \hline
 N2,N3 & 4*50 & 6*10 & 260\\
  \hline
 N2,N4 & 4*80 & 6*10 & 380\\
  \hline
 N3,N4 & 4*70 & 6*30 & 460\\
  \hline
 N1,N2,N3 & 4*20 & 6*60 & 440\\
  \hline
 N1,N2,N4 & 4*50 & 6*60 & 560\\
  \hline
 N1,N3,N4 & 4*40 & 6*80 & 640\\
  \hline
 N2,N3,N4 & 4*30 & 6*70 & 540\\
  \hline
 N1,N2,N3,N4 & 4*0 & 6*90 & 360\\
  \hline
\end{tabular}\\
\normalsize

So the best way is to have copies at N2 and N3.

\section{Exercise 5.3: Majority consensus}

\scriptsize
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
step & node &TS  & input &previous & local & output\\
 &  &for  & &decisions  & decision & \\
 &  &x & &  &  & \\
\hline
 1 & C & 0 & - & - & OK for $T_{C1}$  & To D: OK from C for $T_{C1}$ $TS(T_{C1}) = 1$ \\
\hline
 2 & D & 0 & OK for $T_{C1}$ & OK from C for $T_{C1}$ $TS(T_{C1}) = 1$  &  OK for $T_{C1}$  & To E: OK from D for $T_{C1}$ $TS(T_{C1}) = 1$ \\
 2 & A & 0 & - & - & OK for $T_{A2}$  & To B: OK from A for $T_{A2}$ $TS(T_{A2}) = 2$ \\
\hline
 3 & E & 0 & OK for $T_{C1}$ & OK from D for $T_{C1}$ $TS(T_{C1}) = 1$  & OK for $T_{C1}$  & To F: OK from E for $T_{C1}$ $TS(T_{C1}) = 1$ \\
 3 & B & 0 & OK for $T_{A2}$ & OK from A for $T_{A2}$ $TS(T_{A2}) = 2$  & OK for $T_{A2}$  & To C: OK from B for $T_{A2}$ $TS(T_{A2}) = 2$ \\
 3 & F & 0 & - & - & OK for $T_{F3}$  & To G: OK from F for $T_{F3}$ $TS(T_{F3}) = 3$ \\
\hline
 4 & F & 0 & OK for $T_{C1}$ & OK from D for $T_{C1}$ $TS(T_{C1}) = 1$  & PASS for $T_{C1}$  & To G: PASS from F for $T_{C1}$ $TS(T_{C1}) = 1$ \\
 4 & C & 0 & OK for $T_{A2}$ & OK from B for $T_{A2}$ $TS(T_{A2}) = 2$  & DEFF. for $T_{A2}$  & - \\
 4 & G & 0 & OK for $T_{F3}$ & OK from F for $T_{F3}$ $TS(T_{f3}) = 3$ & OK for $T_{F3}$  & To A: OK from G for $T_{F3}$ $TS(T_{F3}) = 3$ \\

\hline
 5 & G & 0 & PASS for $T_{C1}$ & PASS from F for $T_{C1}$ $TS(T_{C1}) = 1$ & PASS for $T_{C1}$  & To A: PASS from G for $T_{C1}$ $TS(T_{C1}) = 1$ \\
 5 & C & 0 & DEFF. for $T_{A2}$ & - & DEFF. for $T_{A2}$  & - \\
 5 & A & 0 & OK for $T_{F3}$ & OK from G for $T_{F3}$ $TS(T_{F3}) = 3$ & DEFF. $T_{F3}$  & - \\

\hline
 6 & A & 0 & PASS for $T_{C1}$ & PASS from G for $T_{C1}$ $TS(T_{C1}) = 1$ & PASS for $T_{C1}$  & To B: PASS from A for $T_{C1}$ $TS(T_{C1}) = 1$ \\
 6 & C & 0 & DEFF. for $T_{A2}$ & - & DEFF. for $T_{A2}$  & - \\
 6 & A & 0 & DEFF. for $T_{F3}$ & - & DEFF. $T_{F3}$  & - \\

\hline
%REJ. cause majority no longer can be reached
 7 & B & 0 & PASS for $T_{C1}$ & PASS from A for $T_{C1}$ $TS(T_{C1}) = 1$ & REJ. for $T_{C1}$  & To C: GLOBAL REJ. from B for $T_{C1}$ \\
 7 & C & 0 & DEFF. for $T_{A2}$ & - & DEFF. for $T_{A2}$  & - \\
 7 & A & 0 & DEFF. for $T_{F3}$ & - & DEFF. $T_{F3}$  & - \\

\hline
 8 & C & 0 & G. REJ. $T_{C1}$ & GLOBAL REJ. from B for $T_{C1}$ & G. REJ. for $T_{C1}$  & To D: GLOBAL REJ. from C for $T_{C1}$ \\
 8 & C & 0 & DEFF. for $T_{A2}$ & - & OK for $T_{A2}$  & To D: OK from C for $T_{A2}$ $TS(T_{A2}) = 2$ \\
 8 & A & 0 & DEFF. for $T_{F3}$ & - & DEFF. $T_{F3}$  & - \\
\hline
 9 & D & 0 & G. REJ. $T_{C1}$ & GLOBAL REJ. from C for $T_{C1}$ & G. REJ. for $T_{C1}$  & To E: GLOBAL REJ. from D for $T_{C1}$ \\
 9 & D & 2 & OK for $T_{A2}$ & OK from C for $T_{A2}$ $TS(T_{A2}) = 2$ & G. ACC for $T_{A2}$  & To E: GLOBAL ACC. from D for $T_{A2}$ \\
 9 & A & 0 & DEFF. for $T_{F3}$ & - & DEFF. $T_{F3}$  & - \\

\hline
 11 & E & 0 & G. REJ. $T_{C1}$ & GLOBAL REJ. from D for $T_{C1}$ & G. REJ. for $T_{C1}$  & To F: GLOBAL REJ. from E for $T_{C1}$ \\
 11 & E & 2 & G. ACC. $T_{A2}$ & GLOBAL ACC. from D for $T_{A2}$ & G. ACC for $T_{A2}$  & To F: GLOBAL ACC. from E for $T_{A2}$ \\
 11 & A & 0 & DEFF. for $T_{F3}$ & - & DEFF. $T_{F3}$  & - \\

\hline
 12 & F & 0 & G. REJ. $T_{C1}$ & GLOBAL REJ. from E for $T_{C1}$ & G. REJ. for $T_{C1}$  & To G: GLOBAL REJ. from F for $T_{C1}$ \\
 12 & F & 2 & G. ACC.  $T_{A2}$ & GLOBAL ACC. from E for $T_{A2}$ & G. ACC for $T_{A2}$  & To G: GLOBAL ACC. from F for $T_{A2}$ \\
 12 & A & 0 & DEFF. for $T_{F3}$ & - & DEFF. $T_{F3}$  & - \\

\hline
 13 & G & 0 & G. REJ. $T_{C1}$ & GLOBAL REJ. from F for $T_{C1}$ & G. REJ. for $T_{C1}$  & To A: GLOBAL REJ. from G for $T_{C1}$ \\
 13 & G & 2 & G. ACC.  $T_{A2}$ & GLOBAL ACC. from F for $T_{A2}$ & G. ACC for $T_{A2}$  & To A: GLOBAL ACC. from G for $T_{A2}$ \\
 13 & A & 0 & DEFF. for $T_{F3}$ & - & DEFF. $T_{F3}$  & - \\

\hline
 14 & A & 0 & G. REJ. $T_{C1}$ & GLOBAL REJ. from G for $T_{C1}$ & G. REJ. for $T_{C1}$  & To B: GLOBAL REJ. from A for $T_{C1}$ \\
 14 & A & 2 & G. ACC.  $T_{A2}$ & GLOBAL ACC. from G for $T_{A2}$ & G. ACC for $T_{A2}$  & To B: GLOBAL ACC. from A for $T_{A2}$ \\
 14 & A & 2 & DEFF. for $T_{F3}$ & - & G. REJ. for $T_{F3}$  & To B: GLOBAL REJ. from A for $T_{F3}$ \\

\hline
 15 & B & 0 & G. REJ. $T_{C1}$ & GLOBAL REJ. from A for $T_{C1}$ & G. REJ. for $T_{C1}$  & To C: GLOBAL REJ. from B for $T_{C1}$ \\
 15 & B & 2 & G. ACC.  $T_{A2}$ & GLOBAL ACC. from A for $T_{A2}$ & G. ACC for $T_{A2}$  & To C: GLOBAL ACC. from B for $T_{A2}$ \\
 15 & B & 2 & G. REJ. $T_{F3}$ & GLOBAL REJ. from A for $T_{F3}$ & G. REJ. for $T_{F3}$  & To C: GLOBAL REJ. from B for $T_{F3}$ \\

\hline
 16 & C & 0 & G. REJ. $T_{C1}$ & GLOBAL REJ. from B for $T_{C1}$ & -  & - \\
 16 & C & 2 & G. ACC.  $T_{A2}$ & GLOBAL ACC. from B for $T_{A2}$ & G. ACC for $T_{A2}$  & To D: GLOBAL ACC. from C for $T_{A2}$ \\
 16 & C & 2 & G. REJ. $T_{F3}$ & GLOBAL REJ. from B for $T_{F3}$ & G. REJ. for $T_{F3}$  & To D: GLOBAL REJ. from C for $T_{F3}$ \\

\hline
 17 & D & 2 & G. ACC.  $T_{A2}$ & GLOBAL ACC. from C for $T_{A2}$ & -  & - \\
 17 & D & 2 & G. REJ. $T_{F3}$ & GLOBAL REJ. from C for $T_{F3}$ & G. REJ. for $T_{F3}$  & To E: GLOBAL REJ. from D for $T_{F3}$ \\

\hline
 18 & E & 2 & G. REJ. $T_{F3}$ & GLOBAL REJ. from D for $T_{F3}$ & G. REJ. for $T_{F3}$  & To F: GLOBAL REJ. from E for $T_{F3}$ \\

\hline
 18 & F & 2 & G. REJ. $T_{F3}$ & GLOBAL REJ. from E for $T_{F3}$ & G. REJ. for $T_{F3}$  & To G: GLOBAL REJ. from F for $T_{F3}$ \\

\hline
 19 & G & 2 & G. REJ. $T_{F3}$ & GLOBAL REJ. from F for $T_{F3}$ & G. REJ. for $T_{F3}$  & To A: GLOBAL REJ. from G for $T_{F3}$ \\

\hline
 20 & A & 2 & G. REJ. $T_{F3}$ & GLOBAL REJ. from G for $T_{F3}$ & -  & - \\

\hline
\end{tabular}\\
\normalsize


\section{Exercise 5.4: Tree quorum}
  \begin{enumerate}[a)]
  \item Let's number nodes uisng the BSF algorithm(root 1, root's children: 2,3,4 and so on). Combinations of positive votes can be divided into:
    \begin{enumerate}
      \item Root does not accept
        \begin{enumerate}
          \item 1 of root's children accepts i.e. $\{2\}$: we need both:
            \begin{enumerate}
              \item 2 levels below $\{2\}$ accept. This means we need accept in $\{2\}$ children trees with 2 levels, what is the same as example from lecture with $(h = 3, v = 3)$. I. e. we get combinations: $\{2, 5, 14, 15, 6, 17, 18\}$ or $\{2, 5, 41, 42, 44, 45, 6, 50, 51, 53, 54\}$.
              \item 3 levels below $\{3\}$ or $\{4\}$ to accept: 2 their children, and their children and their children accept. I.e.$\{8, 9, 23, 24, 26, 27, 71, 72, 74, 74\}$.
            \end{enumerate}
            Summing up the above examples we get combinations:
            \begin{itemize}
              \item
                $\{2, 5, 14, 15, 6, 17, 18, 8, 9, 23, 24, 26, 27, 71, 72, 74, 74\}$  
              \item
                $\{2, 5, 41, 42, 44, 45, 6, 50, 51, 53, 54, 8, 9, 23, 24, 26, 27, 71, 72, 74, 74\}$.
            \end{itemize}
          \item any 2 of root's children accept i.e. $\{2,3\}$ We need 2 levels below $\{2\}$ and $\{3\}$ to accept. See: a) i. A).
          \item None of root's children accepts: we need that there are 2 roots children that's 2 children accept, and their 2 children accept, and their 2 children also accept. I.e. the firts combination in lexical order is $\{5,6, 14, 15, 41, 42, 44, 45, 8, 9, 23, 24, 26, 27, 68, 69, 71, 72\}$.
        \end{enumerate}
      \item Root accepts. We need two levels below root to accept.
        \begin{enumerate}
           \item any 2 of root's children accept i. e. $\{2,3\}$ We need 2 their children accept $\{5, 6, 8, 9\}$ or 8 their granchildren that have common parents to accept i.e. $\{14, 15, 17, 18, 23, 24, 26, 27\}$ or 16 their grandgrandchildren with common grandparents accept i.e.\\ $\{41, 42, 44, 45, 50, 51, 53, 54, 71, 72, 74, 75, 80, 81, 83, 84\}$.
          \item 1 of root's children accepts i.e. $\{2\}$: we need both:
            \begin{enumerate}
              \item $\{2\}$'s 2 children accept i.e. $\{5,6\}$ or their 4 grandchidren with common parents accept: $\{14, 15, 17, 18\}$ or their 8 grandgrandchildren with common grandparents accept: $\{41, 42, 44, 45, 50, 51, 53, 54\}$ or combinations of above i.e. one children and 2 grandchildren...
              \item 2 levels below $\{3\}$ or $\{4\}$ accept. Let's choose $\{3\}$ without loss of generality. We have similar situation to previous except that we need both children and grandchildren or children and grandgrandchildren to accept.
            \end{enumerate}
          \item None of root's children accepts.
                We need 2 levels below 2 children to accept. It's similar to ii) B.
       \end{enumerate}
    \end{enumerate}
  \item Write quorum to avoid write-write conflicts: $q_{w} = (2, 3)$. Than we get read quorum: $q_{r} = (2, 2)$ to avoid read-write conflicts. Read request conditions are easier to fulfil, so they are preffered.
  \item We need to set $q_{r} = (2, 3)$ to obtain no preference for read quorum.
  \end{enumerate}
\end{document}
